package Arithmetic;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-10-27
 * Time: 13:59
 */
//滑动窗口
public class SlidingWindow {
    public static int ret = 0;
    //209.长度最小的数组

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param target 目标值
     * @param nums 目标数组
     * @return 最小长度
     */
    public static int minSubArrayLen(int target, int[] nums) {
        //定义双指针
        int left = 0;
        int sum = 0;//记录当前窗口和
        int minLen = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length;right++) {
            if(sum < target){
                sum += nums[right];
            }
            while(sum >= target){
                //更新最小长度
                minLen = Math.min(minLen,right - left + 1);
                sum -= nums[left++];
            }
        }
        if(left == 0) return 0;
        return minLen;
    }

    //LCR 16.无重复字符的最长子串

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     * @param ss 目标字符串
     * @return 最长子串长度
     */
    public static int lengthOfLongestSubstring(String ss) {
        //定义双指针
        int i = 0;
        int j = 0;

        int maxLen = 0;
        //使用HashSet存储字符Key - 字符
        HashSet<Character> set = new HashSet<>();
        char[] s = ss.toCharArray();
        for (; j < s.length; j++) {
            if(!set.contains(s[j])){
                set.add(s[j]);
            }else{//更新最长长度
                maxLen = Math.max(maxLen,j - i);
                //循环判断窗口是否还右重复字符，直到找到重复字符结束循环
                while(set.contains(s[j])){
                    set.remove(s[i++]);
                }
                //虽然窗口内的重复元素移除，但是新的窗口还应该包含当前重复元素，避免遗漏
                set.add(s[j]);
            }
        }
        //避免"    hel"情况遗漏刚好最后的j - i区间为最长子串
        return Math.max(maxLen,j - i);
    }

    //1004.最大连续1的个数

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param nums 目标数组
     * @param k 可以翻转的零个数
     * @return 最长子串
     */
    public static int longestOnes(int[] nums, int k) {
        //定义双指针
        int left = 0;
        int right = 0;

        int maxLen = 0;//更新最长长度

        int count  = 0;//记录当前维护的窗口零个数
        for (; right < nums.length; right++) {
            if(nums[right] == 0) count++;
            //缩小做窗口，找到多出来的0,让窗口合法
            while(count > k){
                if(nums[left++] == 0) count--;

            }
            //更新操作放到这里保证不会遗漏掉任何情况
            maxLen = Math.max(maxLen,right - left + 1);
        }
        return maxLen;
    }

    //1658.将X减到0的最小操作数

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param nums 目标数组
     * @param x 要消除的数X
     * @return 最小操作数
     */
    public static int minOperations(int[] nums, int x) {
        //定义双指针
        int left = 0;
        int right = 0;

        //计算数组总和
        int Sum = 0;
        for (int i:nums) Sum+=i;
        Sum -= x;

        if(Sum < 0) return -1;
        int maxLen = -1;//记录最长子串
        int windowSum = 0;//窗口和
        for (; right < nums.length; right++) {
            //进窗口
            windowSum += nums[right];

            //判断
            while(windowSum > Sum){
                //出窗口，为什么不是>=，这里可以保证出了该循环windowSum<=Sum,在进行一次额外判断即可
                windowSum -= nums[left++];
            }

            //更新结果
            if(windowSum == Sum)
                maxLen = Math.max(maxLen,right - left + 1);
        }
        if(maxLen == -1) return -1;
        return nums.length - maxLen;
    }

    //438.找到字符串中所有字母的异位词

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param ss
     * @param pp
     * @return
     */
    public static List<Integer> findAnagrams(String ss, String pp) {
        //将字符串转化为字符数组，方便操作
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        //创建哈希表map1,map2
        //map1作为对照表，map2维护窗口字母个数
        HashMap<Character,Integer> map1 = new HashMap<>();
        HashMap<Character,Integer> map2 = new HashMap<>();

        //对照表
        for (Character ch:p) map1.put(ch, map1.getOrDefault(ch,0) + 1);

        List<Integer> ret = new LinkedList<>();//容器
        int count = 0;//计数器

        //定义双指针
        int left = 0;
        int right = 0;
        while (right < s.length) {
            //进窗口
            map2.put(s[right],map2.getOrDefault(s[right],0) + 1);
            if(map1.getOrDefault(s[right],0).equals(map2.getOrDefault(s[right],0))) count++;

            //判断
            if(right - left + 1 == p.length){
                //更新结果
                if(count == map1.size()){
                    ret.add(left);
                }
                //出窗口
                if(map1.containsKey(s[left]) && map1.get(s[left]).equals(map2.get(s[left]))) count--;
                map2.put(s[left],map2.get(s[left++]) - 1);
            }
            right++;
        }
        return ret;
    }

    //30.串联所有单词的子串

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     * @param s 字符串
     * @param words 单词数组
     * @return 所有子串起始下标
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new LinkedList<>();

        int wordLen = words[0].length();//单词长度大小

        HashMap<String,Integer> map1 = new HashMap<>();
        HashMap<String,Integer> map2 = new HashMap<>();

        //对照表
        for (String ss:words){
            map1.put(ss,map1.getOrDefault(ss,0) + 1);
        }

        //滑动窗口执行次数:单词长度大小
        for (int i = 0; i < wordLen; i++) {
            int count = 0;//新的循环，重新更新计数器值
            map2 = new HashMap<>();//新的循环，重新更新哈希表
            int cur = i;//标记子串起始位置
            //定义双指针，每次移动的步数为单词长度
            int left = i;
            int right = left + wordLen;
            while(right <= s.length()){//包括等于情况
                //进窗口
                String word = s.substring(left,right);//截取单词
                map2.put(word,map2.getOrDefault(word,0) + 1);

                if(map1.getOrDefault(word,0).equals(map2.getOrDefault(word,0))){//单词个数相等
                    count++;
                }

                //判断
                if(right - cur == wordLen * words.length){
                    //更新结果
                    if(count == map1.size()){
                        list.add(cur);
                    }

                    String prevWord = s.substring(cur,cur + wordLen);
                    if(map1.getOrDefault(prevWord,0).equals(map2.getOrDefault(prevWord,0))){
                        count--;//判断单词种类是否需要减少
                    }
                    //出窗口
                    map2.put(prevWord,map2.getOrDefault(prevWord,0) - 1);
                    cur += wordLen;
                }
                left = right;
                right += wordLen;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        //209.长度最小的数组
        int[] array1 = {2,3,1,2,4,3};
        int minLen = minSubArrayLen(7,array1);
        System.out.println(minLen);

        //LCR 16.无重复字符的最长子串
        String str = "   cbd";
        ret = lengthOfLongestSubstring(str);
        System.out.println(ret);

        //1004.最大连续1的个数
        int[] array2 = {3,2,20,1,1,3};
        int result = longestOnes(array2,10);
        System.out.println(result);

        //1658.将X减到0的最小操作数
        int[] array3 = {5,2,3,1,1};
        ret = minOperations(array3,5);
        System.out.println(ret);

        //438.找到字符串中所有字母的异位词
        String str1 = "abababab";
        String str2 = "abc";
        List<Integer> list = findAnagrams(str1,str2);
        System.out.println(list);

        //30.串联所有单词的子串
        String s = "dddddddddddd";
        String[] words = {"dddd","dddd"};
        list = findSubstring(s,words);
        System.out.println(list);
    }
}
